package jjn.round1;

/**
 * @author Jjn
 * @since 2022/11/12 17:07
 */
public class LeetCode494_TargetSumSolution2 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < target) {
            return 0;
        }
        if ((sum - target) % 2 != 0) {
            return 0;
        }
        int total = (sum - target) / 2;
        int[][] dp = new int[nums.length + 1][total + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= nums.length; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= total; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][total - num];
                }
            }
        }
        return dp[nums.length][total];
    }
}
